package com.asia.algorithmcode.dynamicProgram;

import com.asia.algorithmcode.binaryTree.HasPathSum;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * @DESCRIPTION:
 * @USER: wanfu
 * @DATE: 2025/6/9 星期一 15:52
 */
public class MaxPathSum {

    public static void main(String[] args) {
        TreeNode root = new TreeNode(-10);
        TreeNode t9 = new TreeNode(9);
        TreeNode t20 = new TreeNode(20);
        TreeNode t15 = new TreeNode(15);
        TreeNode t7 = new TreeNode(7);

        root.left = t9;
        root.right = t20;
        t20.left = t15;
        t20.right = t7;

        System.out.println(new MaxPathSum().maxPathSum(root));
    }

    public int maxPathSum(TreeNode root) {
        maxValue(root);
        return res;
    }

    Integer res = Integer.MIN_VALUE;

    private int maxValue(TreeNode root) {
        if (root == null) {
            return 0;
        }

        int left = Math.max(maxValue(root.left), 0);
        int right = Math.max(maxValue(root.right), 0);

        int sum = root.val + left + right;

        res = Math.max(res, sum);

        return root.val + Math.max(left, right);
    }
}
